package com.wjy.Data_Structure.linearlist.listslinkimpl;

import com.wjy.Data_Structure.linearlist.common.DLNode;
import com.wjy.Data_Structure.linearlist.common.Iterator;
import com.wjy.Data_Structure.linearlist.common.LinkedList;
import com.wjy.Data_Structure.linearlist.common.Node;
import com.wjy.Data_Structure.linearlist.exception.InvalidNodeException;
import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException;

//基于双向链表实现的链接表
public class LinkedListDLNode implements LinkedList {
	private int size; // 规模
	private DLNode head; // 头结点
	private DLNode tail; // 尾结点

	// 构建只有头尾结点的链表

	public LinkedListDLNode() {
		this.size = 0;
		this.head = new DLNode();
		this.tail = new DLNode();
		this.head.setNext(tail);
		tail.setPre(this.head);
	}

	// 辅助方法，判断结点 p 是否合法，如合法转换为 DLNode
	protected DLNode checkPosition(Node p) throws InvalidNodeException {
		if (p == null) {
			throw new InvalidNodeException("错误：p 为空。");
		}
		if (p == head) {
			throw new InvalidNodeException("错误：p 指向头节点，非法.");
		}
		if (p == tail) {
			throw new InvalidNodeException("错误：p 指向尾结点，非法.");
		}
		DLNode node = (DLNode) p;
		return node;

	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public Node first() throws OutOfBoundaryException {
		if (isEmpty()) {
			throw new OutOfBoundaryException("错误，链接表为空");
		}
		return head.getNext();
	}

	@Override
	public Node last() throws OutOfBoundaryException {
		if (isEmpty()) {
			throw new OutOfBoundaryException("错误：链接表为空");
		}
		return tail.getPre();
	}

	@Override
	public Node getNext(Node p) throws InvalidNodeException, OutOfBoundaryException {
		DLNode node = checkPosition(p);
		node = node.getNext();
		if (node == tail)
			throw new OutOfBoundaryException("错误： 已经是链接表尾端");
		return node;
	}

	@Override
	public Node getPre(Node p) throws InvalidNodeException, OutOfBoundaryException {
		DLNode node = checkPosition(p);
		node = node.getPre();
		if (node == head)
			throw new OutOfBoundaryException("错误：已经是链接表前段");
		return null;
	}

	@Override
	public Node insertFirst(Object e) {
		DLNode node = new DLNode(e, head, head.getNext());
		head.getNext().setPre(node);
		head.setNext(node);
		size++;
		return node;
	}

	@Override
	public Node insertLast(Object e) {
		DLNode node = new DLNode(e, tail.getPre(), tail);
		tail.getPre().setNext(node);
		tail.setPre(node);
		size++;
		return node;
	}

	@Override
	public Node insertAfter(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		DLNode newNode = new DLNode(e, node, node.getNext());
		node.getNext().setPre(newNode);
		node.setNext(newNode);
		size++;
		return newNode;
	}

	@Override
	public Node inserBefore(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		DLNode newNode = new DLNode(e, node.getPre(), node);
		node.getPre().setNext(newNode);
		node.setPre(newNode);
		size++;
		return newNode;
	}

	@Override
	public Object remove(Node p) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		Object obj = node.getData();
		node.getPre().setNext(node.getNext());
		node.getNext().setPre(node.getPre());
		size--;
		return obj;
	}

	@Override
	public Object removeFirst() throws InvalidNodeException {
		return remove(head.getNext());
	}

	@Override
	public Object removeLast() throws InvalidNodeException {
		return remove(tail.getPre());
	}

	@Override
	public Object replace(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		Object obj = node.getData();
		node.setData(e);
		return obj;
	}

	@Override
	public Iterator elements() {
		return new LinkedListIterator(this);
	}

}
